#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

string getPermutation(int n, int k) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(n==1)
        return string("1");
    // init zero string

    char ch[10];
    int i;
    for(i=1; i<=n; ++i){
        ch[i-1] = i + '0';
    }
    ch[i-1] = '\0';
    string zeroString(ch);
    
    for(int i=1; i<k; ++i){
        // find the one with cloest greater than it
        for(int j=zeroString.size()-1; j>=0; --j){
            int curNum = zeroString[j] - '0';
            int cloestIndex = -1;
            for(int t=j+1; t<zeroString.size(); ++t){
                if((zeroString[t]-'0') > curNum){
                    if(cloestIndex == -1){
                        cloestIndex = t;
                    }
                    else if((zeroString[cloestIndex]-'0'-curNum) > 
                        (zeroString[t]-'0'-curNum)){
                        cloestIndex = t;
                    }
                }
            }
            if(cloestIndex != -1){
                // swap
                char tmp = zeroString[j];
                zeroString[j] = zeroString[cloestIndex];
                zeroString[cloestIndex] = tmp;
                // sort
                sort(zeroString.begin() + j + 1, zeroString.end());
                break;
            }
        }
    }

    return zeroString;

}

string getPermutation2(int n, int k) {
    unsigned int nn = 1;
    vector<unsigned int> nums;
    string res;

    for(int i=1; i<=n; ++i){
        nn *= i;
        nums.push_back(i);
    }

    --k;
    for(int i=0; i<n; ++i){
        nn /= n-i;
        int pickIndex = k/nn;
        res.push_back(nums[pickIndex] + '0');
        nums.erase(nums.begin() + pickIndex);
        k %= nn;
    }
    return res;
}


int main(){
    getPermutation2(2,1);
}